/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM90 最小覆盖子串
 * <a href="https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac?tpId=295&tqId=670&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-07-06
 * Time: 22:05
 */
public class Solution {
    /**
     * 解题思路: (滑动窗口+哈希)
     * 首先,我们应该想到的是如何快速的判断 s 的一个子串是否包含 t 中所有的字符,这里因为
     * 题目中规定,字符串只有大小写英文字母,因此这里可以做一个 hash数组 来记录每个字符出现
     * 的次数,即先遍历 t 字符串中的每一个字符,遍历到每一个字符的时候,将 hash数组 对应位
     * 置的数减一,之后在遍历 t 字符串的时候,维护 hash数组 ,即遍历到对应元素,就将对应位置
     * 加一,之后每次判断的时候只需要遍历这 52 个位置,如果全大于 0 ,即包含了 t 中所有的字
     * 符,否则就没有包含 t 中所有的字符.
     * 之后,因为这里要找 s 中最短的连续子串,因此这里考虑使用滑动窗口来判断,即维护窗口的左右
     * 下标分别为 left 和 right ,如果 [left,right] 区间内的子串包含 t 中所有的字符,则
     * left++,寻找最小区间,而如果 [left,right] 区间内的子串没有包含 t 中所有的字符,则
     * right++, 寻找包含 t 中所有字符的区间.遍历过程中维护最小区间即可.
     * 最后,如果遍历 t 区间后,发现 left == 0,即 s 中的任何子串都没有含 t 中所有的字符,
     * 返回空串即可.
     */
    public String minWindow (String S, String T) {
        // 检验合法性
        if (T.length() == 0 || S.length() < T.length()) {
            return "";
        }
        // 先将 T 字符串中的字符哈希
        int[] hash = new int[128];
        for (int i = 0; i < T.length(); i++) {
            hash[T.charAt(i)]--;
        }
        // 滑动窗口判断最小区间
        int left = 0;
        int temp = 0;                       // 记录最小区间的左边界
        int minSize = Integer.MAX_VALUE;    // 记录最下区间的字符个数
        for (int right = 0; right < S.length(); right++) {
            hash[S.charAt(right)]++;
            // 如果符合条件就缩小区间,寻找最小区间
            while (check(hash)) {
                if (right-left+1 < minSize) {
                    temp = left;
                    minSize = right-left+1;
                }
                hash[S.charAt(left)]--;
                left++;
            }
        }
        if (left == 0) {
            return "";
        } else {
            return S.substring(temp,temp+minSize);
        }
    }

    /**
     * 利用检验 52 个英文大小写的位置是否全部 >=0
     * 的方法来判断当前子串是否包含 t 中的所有字符
     * @param hash
     * @return
     */
    private boolean check (int[] hash) {
        for (int i = 'a'; i <= 'z'; i++) {
            if (hash[i] < 0) {
                return false;
            }
        }
        for (int i = 'A'; i <= 'Z'; i++) {
            if (hash[i] < 0) {
                return false;
            }
        }
        return true;
    }
}
